home *** CD-ROM | disk | FTP | other *** search
- Path: sun001.spd.dsccc.com!spd!jmccarty
- From: jmccarty@spd.dsccc.com (Mike McCarty)
- Newsgroups: comp.lang.pascal.misc,comp.lang.c++,comp.lang.c,comp.lang.pascal.borland
- Subject: Re: Tough FACTORIAL math problem...
- Date: 20 Feb 1996 20:36:15 GMT
- Organization: DSC Communications Corporation, Plano, Texas USA
- Message-ID: <4gdbbv$l1r@sun001.spd.dsccc.com>
- References: <4fr8be$ass@news.iconn.net> <4g0giv$94s@sun132.spd.dsccc.com> <4gbsir$opr@axl02it.ntc.nokia.com>
- NNTP-Posting-Host: aplo139.spd.dsccc.com
-
- In article <4gbsir$opr@axl02it.ntc.nokia.com>,
- Risto Lankinen <risto.lankinen@ntc.nokia.com> wrote:
- )Hi!
- )
- )kcline@sun132.spd.dsccc.com (Kevin Cline) wrote:
- )>In article <4fr8be$ass@news.iconn.net>, The Crow <thecrow@iconn.net>
- )>wrote:
- )>>Here is what I am trying to do, I want to find the last NON-ZERO digit
- )>>of a given factorial. For instance,
- )>>
- )>>5! = 120
- )>>
- )>>so the last non-zero digit is 2. ...
- )
- ) [a suggested solution deleted]
- )
- )>This solution runs in O(n). With a bit more thought a log(n) solution
- )>is possible.
- )
- )There is an algorithm that calculates the last non-zero _binary_ digit
- )of ANY factorial - with SUB-LOGARITHMIC time even in the worst case!!!
- )
- )Mail me if interested but be prepared to explain what you need it for.
- )The algorithm is indeed very VERY fast, and so I don't want to give it
- )away without being credited at least. Also, please mention "rightmost
- )non-zero binary digit algorithm" in your request.
- )
- )terv: Risto
-
- Through crafty net espionage, I have managed to obtain a copy of
- Risto's algorithm. It's truly amazing! He did it with a single line
- macro, so it is even automatically inlined! And it is really, really (I
- mean really) fast! I am willing to sell copies of this macro to anyone
- for $5.00 per person, but only for the first 1000 who ask. Oh, one
- condition of sale is: do not under any circumstances let anyone know
- where you got the algorithm, especially don't tell Risto, since he
- would be angry if he found out that I had penetrated his security.
-
- Mike
- ----
- char *p="char *p=%c%s%c;main(){printf(p,34,p,34);}";main(){printf(p,34,p,34);}
-
- I don't speak for DSC. <- They make me say that.
-